class code6 {
    List<String> ret;
    StringBuffer path;
    String[] hash = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        path = new StringBuffer();
        ret = new ArrayList<>();
        if(digits.length() == 0) {
            return ret;
        }
        dfs(digits,0);
        return ret;
    }

    public void dfs(String digits,int pos) {
        if(digits.length() == path.length()) {
            ret.add(path.toString());
            return;
        }
        String cur = hash[digits.charAt(pos)-'0'];
        for(int i=0;i<cur.length();i++) {
            path.append(cur.charAt(i));
            dfs(digits,pos+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}